﻿#pragma once
#include "Index.h"

/**
 * 俄罗斯套娃信封问题.
 * https://leetcode.cn/problems/russian-doll-envelopes/
 */
class RussianDollEnvelopes
{
	FRIEND_TEST(RussianDollEnvelopesTest, maxEnvelopes);
private:
	typedef std::vector<int> EnvelopeExtent;
	enum ExtentType
	{
		WIDTH = 0,
		HEIGHT = 1,
	};

public:
	/*
	 * 标题：实现信封套娃最多层数算法
	 * 关键词：算法，信封，最多层数，信封套娃，排序，向量，二分搜索
	 *
	 * 这段代码实现了一个算法，可以给定一组信封，求出它们能构成的最多层数的信封套娃。
	 *
	 * 算法的实现步骤如下：
	 * 1、按照宽度从小到大的顺序对信封进行排序，如果宽度相同，则按照高度从大到小的顺序排序。
	 * 2、对于排序后的信封数组，用一个向量记录它们能构成的最长信封套娃的序列（即信封套娃的顶部）。
	 * 3、对于每个新的信封，如果它可以包含在当前信封套娃的顶部，则将其加入信封套娃序列的末尾；
	 *    否则，用二分搜索找出第一个不能被该信封包含的信封，并用该信封替换它（可以保证用该信封替换后，信封套娃序列依然是最长的）。
	 * 4、重复步骤 3，直到处理完所有信封为止。最后，返回信封套序列的长度即可
	 */
	int maxEnvelopes(std::vector<EnvelopeExtent>& envelopes)
	{
		if (envelopes.empty())
			return 0;
		const int arrSize = envelopes.size();
		sortEnvelopes(envelopes);

		std::vector<EnvelopeExtent*> dp;
		for (int i = 0; i < arrSize; ++i)
			updateDP(dp, &envelopes[i]);

		return dp.size();
	}
private:
	void sortEnvelopes(std::vector<EnvelopeExtent>& envelopes)
	{
		std::sort(envelopes.begin(), envelopes.end(), [](EnvelopeExtent& left, EnvelopeExtent& right)->bool
			{
				if (left[WIDTH] == right[WIDTH])
					return left[HEIGHT] > right[HEIGHT];
				else
					return left[WIDTH] < right[WIDTH];
			});
	}

	bool canContains(EnvelopeExtent* larger, EnvelopeExtent* smaller)
	{
		if (!larger || !smaller)
			return false;
		return larger->at(WIDTH) > smaller->at(WIDTH) &&
			larger->at(HEIGHT) > smaller->at(HEIGHT);
	}

	void updateDP(std::vector<EnvelopeExtent*>& dp, EnvelopeExtent* envelope)
	{
		if (dp.empty())
		{
			dp.emplace_back(envelope);
			return;
		}

		if (canContains(envelope, dp.back()))
		{
			dp.emplace_back(envelope);
			return;
		}

		int notContainIndex = dp.size();
		int dpLeft = 0, dpRight = dp.size() - 1;
		while (dpLeft <= dpRight)
		{
			const int mid = (dpLeft + dpRight) >> 1;
			if (canContains(envelope, dp[mid]))
			{
				notContainIndex = mid + 1;
				dpLeft = mid + 1;
			}
			else
			{
				notContainIndex = mid;
				dpRight = mid - 1;
			}
		}

		if (notContainIndex < dp.size())
			dp[notContainIndex] = envelope;
	}
};
#ifdef DEV_TEST
#include <gtest/gtest.h>
TEST(RussianDollEnvelopesTest, maxEnvelopes)
{
	RussianDollEnvelopes solution;

	const int testTimes = 500;
	for (int testTime = 0; testTime < testTimes; ++testTime)
	{
		std::vector<RussianDollEnvelopes::EnvelopeExtent> envelopes;
		for (int i = 0; i < 500; ++i)
		{
			envelopes.emplace_back(RussianDollEnvelopes::EnvelopeExtent
				{ TestingUtil::randIntBetween(1,20),TestingUtil::randIntBetween(1,20) });
		}

		const int size = envelopes.size();

		std::vector<RussianDollEnvelopes::EnvelopeExtent> orderEnvelopes = envelopes;
		solution.sortEnvelopes(orderEnvelopes);
		std::vector<int> dp(size, 1);
		int maxLen = 1;
		for (int i = 1; i < size; ++i)
		{
			for (int j = 0; j < i; ++j)
			{
				if (solution.canContains(&orderEnvelopes[i], &orderEnvelopes[j]))
				{
					dp[i] = std::max<>(dp[j] + 1, dp[i]);
					maxLen = std::max<>(dp[i], maxLen);
				}
			}
		}

		ASSERT_EQ(solution.maxEnvelopes(envelopes), maxLen) << FormatedUtil::dumpFormated(envelopes);
	}
}
#endif